#include <iostream>

#include "common_list.h"

using namespace std;

class Solution {
public:
    ListNode *EntryNodeOfLoop(ListNode *pHead) {
        ListNode *slow, *fast;
        slow = fast = pHead;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                break;
            }
        }

        if (fast == nullptr || fast->next == nullptr)
            return nullptr;

        ListNode *newHead = pHead;
        while (slow != newHead) {
            newHead = newHead->next;
            slow    = slow->next;
        }
        return newHead;
    }
};

int main(void) {
    cout << "寻找有环链表的入口处：看讲解，相遇点离入口处的距离与头结点到入口处"
            "的"
            "位置相等"
         << endl;
    cout << "所以从相遇处开始与头结点再开始一起往前走，再次相遇点就是入口"
         << endl;
    cout << "https://www.nowcoder.com/practice/"
            "253d2c59ec3e4bc68da16833f79a38e4?tpId=295&tqId=605&ru=%2Fpractice%"
            "2Fd8b6b4358f774294a89de2a6ac4d9337&qru=%2Fta%2Fformat-top101%"
            "2Fquestion-ranking&sourceUrl=%2Fexam%2Foj"
         << endl;

    auto head = generate_cycle_list(3, 0);
    print_list(head);

    auto entry = (new Solution())->EntryNodeOfLoop(head);
    print_list(entry);
    return 0;
}